# 买卖股票的最佳时机: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

# 我只想出来暴力破解~ 但是其实静下心，一步步推，应该是可以发现 下面的求法的
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        """ 暴力破解 """
        n = len(prices)
        rst = 0
        for i in range(n - 1, -1, -1):
            for j in range(i, -1, -1):
               rst = max(prices[i] - prices[j], rst) 
        
        return rst

        

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        """ 答案太巧妙了！ 我们计算每一天能最多买多少钱， 去卖得最多的那一天， 就是赚的最多的
            那么如果保证 今天赚的最多呢？ 只需要再之前那些天中，股票最低价购买。 

            1. 那么 维护当前最小值， 只需要一个变量， 遍历时即可确定。 
            2. 当天能卖得最多的钱，也能求出， max（cur, max_prices）
            总体时间复杂度为 O(n)
            空间复杂度为 O(1)
        """
        n = len(prices)
        rst = 0
        minPrices = 100000000000000
        for i in range(n):
            rst = max(prices[i] - minPrices, rst)
            minPrices = min(prices[i], minPrices)
            
        return rst
